package review;

import javax.swing.plaf.nimbus.State;
import java.util.Arrays;
import java.util.Stack;

/**
 * @author 郝文雪
 * @date 2022/7/24 19:57
 * @Description Test
 */
public class quickSort {
    //递归的快排
    public static void quicksort(int[] arr){
        quickSortInter(arr,0,arr.length-1);
    }

    private static void quickSortInter(int[] arr, int left, int right) {
        if(left>=right) return;

        //采用三数取中值法确定基准值
        int midValIndex=findMidValIndex(arr,left,right);
        swap(arr,midValIndex,left);

        //找出基准值
        int partition=partition(arr,left,right);
        quickSortInter(arr,left,partition-1);
        quickSortInter(arr,partition+1,right);
    }

    private static void swap(int[] arr, int x, int y) {
        int tmp=arr[x];
        arr[x]=arr[y];
        arr[y]=tmp;
    }

    private static int findMidValIndex(int[] arr, int start,int end) {
        int mid=(end-start)/2+start;
        if(arr[start]<arr[end]){
            if(arr[mid]<arr[start]){
                return start;
            }else if(arr[mid]>arr[end]){
                return end;
            }else{
                return mid;
            }
        }else{
            if(arr[mid]>arr[start]){
                return start;
            }else if(arr[mid]<arr[end]){
                return end;
            }else{
                return mid;
            }
        }
    }

    private static int partition(int[] arr, int start, int end) {
        int tmp=arr[start];
        while(start<end){
            while(start<end && arr[end]>=tmp){
                end--;
            }
            arr[start]=arr[end];
            while(start<end && arr[start]<=tmp){
                start++;
            }
            arr[end]=arr[start];
        }
        arr[start]=tmp;
        return start;
    }


    //非递归的快排
    public static void quicksort2(int[] arr){
        Stack<Integer> stack=new Stack<>();
        int left=0;
        int right=arr.length-1;
        int pivot=partition(arr,left,right);
        if(pivot>left+1){//左边有两个元素
            stack.push(left);
            stack.push(pivot-1);
        }
        if(pivot<right-1){
            stack.push(pivot+1);
            stack.push(right);
        }
        while(!stack.isEmpty()){
            right=stack.pop();
            left=stack.pop();

            pivot=partition(arr,left,right);
            if(pivot>left+1){
                stack.push(left);
                stack.push(pivot-1);
            }
            if(pivot<right-1){
                stack.push(pivot+1);
                stack.push(right);
            }
        }
    }


    public static void main(String[] args) {
        int[] arr={5,3,2,1,4,19,42,4,6};
        quicksort2(arr);
        System.out.println(Arrays.toString(arr));
    }
}
